/*
 * Given a string S, find the longest palindromic substring in S.
 * You may assume that the maximum length of S is 1000, and
 * there exists one unique longest palindromic substring.
 */
#include <stdio.h>

char *longestPalindrome(char *s) {
    if (s == NULL) {
        return NULL;
    }

    int *p;
    int len = strlen(s);
    p = (int *) malloc(sizeof(int *) * len);
    memset(p, 0, sizeof(int *) * len);

    int i, j;
    int odd, even;
    for (i = 0; i < len; i++) {
        odd = 1;
        even = 1;
        for (j = 1; i >= j && i + j < len; j++) {
            if (s[i - j] == s[i + j]) {
                if (j == 1) odd = 1;
                odd += 2;
            } else {
                break;
            }
        }
        if (s[i] == s[i + 1]) {
            even = 2;
            for (j = 1; i >= j && i + j + 1 < len; j++) {
                if (s[i - j] == s[i + j + 1]) {
                    even += 2;
                } else {
                    break;
                }
            }
        }
        p[i] = even > odd ? even : odd;
    }
    int max, index;
    char *st = NULL;
    max = 0;
    index = 0;
    for (i = 0; i < len; i++) {
        if (p[i] > max) {
            max = p[i];
            index = i;
        }
    }
    st = (char *) malloc(sizeof(char) * max + 1);
    j = max & 1 ? (max - 1) / 2 : (max - 2) / 2;
    for (i = 0; i < max; i++) {
        st[i] = s[index - j + i];
    }
    st[i] = '\0';
    return st;
}

int main() {
    char *p;
    char *s;
    s = "ddddd";
    p = longestPalindrome(s);
    int i;
    int len = strlen(p);
    printf("st---%d\n", len);
    for (i = 0; i < len; i++) {
        printf("%c\n", *(p + i));
    }
}
